package pro.softzhang.algo.lc900;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.difficulty.DRed;

import java.util.LinkedList;
import java.util.Queue;

@DRed
public class LC919_CompleteBinaryTreeInserter {
    public static void main(String[] args) {

    }

    static class CBTInserter {
        private Queue<TreeNode> queue;
        private TreeNode root;

        public CBTInserter(TreeNode root) {
            this.root = root;

            queue = new LinkedList<>();
            queue.offer(root);
            while (queue.peek().left != null && queue.peek().right != null) {
                TreeNode node = queue.poll();
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }

        public int insert(int v) {
            TreeNode newNode = new TreeNode(v), parent = queue.peek();
            if(parent.left == null) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
                queue.poll();
                queue.offer(parent.left);
                queue.offer(parent.right);
            }
            return parent.val;
        }

        public TreeNode get_root() {
            return root;
        }
    }
}